import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:排序
 * User: Admin
 * Date: 2022-05-26
 * Time: 16:29
 */


public class TestDemo {
    /**
     * 插入排序
     * 适合数据量小,且已经趋于有序的时候使用
     * 空间复杂度O（1）
     * 时间复杂度最坏情况O（n^2） 逆序
     * 时间复杂度最好情况O（n）
     */

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int j = 0;
            int tmp = array[i];
            for (j = i-1; j >=0; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /**
     * 希尔排序
     * @param array
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while(gap > 1) {
            shell(array,gap);
            gap = gap/2;
        }
        shell(array,1);
    }

    public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = 0;
            for (j = i - gap ; j >= 0 ; j-=gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                } else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    /**
     * 选择排序
     * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int index = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[index]) {
                    index = j;
                }
            }
           Swap(array,i,index);
        }
    }

    public static void Swap(int[] array,int index,int end) {
        int tmp = array[index];
        array[index] = array[end];
        array[end] = tmp;
    }

    /**
     * 堆排序
     */
    public static void shiftDown(int[] array,int parent,int end) {
        int child = parent*2+1;
        while(child < end) {
            if(child+1 < end && array[child] < array[child+1]) {
               child++;
            }

            if(array[child] > array[parent]) {
                Swap(array,child,parent);
                parent = child;
                child = parent*2+1;
            } else {
                break;
            }
        }
    }
    public static void createHeap(int[] array) {
        for (int i = (array.length-1-1)/2; i >= 0; i--) {
            shiftDown(array,i,array.length);
        }
    }

    public static void heapSort(int[] array) {
        int end = array.length - 1;

        while(end > 0) {
            Swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    /**
     *
     * 冒泡排序
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j+1]) {
                    Swap(array,j,j+1);
                    flg = true;
                }
            }
            if(!flg) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] array ={20,80,70,50,33,22};
        bubbleSort(array);
       /* createHeap(array);
        heapSort(array);*/
        /*selectSort(array);*/
        /*insertSort(array);*/
        /*shellSort(array);*/
        System.out.println(Arrays.toString(array));
    }
}
